package Test_1204;

import java.util.Arrays;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Heap {
    public int[] elem;//数组
    public int usedSize;//使用大小
    public Heap() {
        this.elem=new int[10];
    }
    //初始化
    public void initHeap(int[] elem){
        for (int i = 0; i <elem.length ; i++) {
            //初始化
            this.elem[i]=elem[i];
            //使用大小增加
            usedSize++;
        }
    }
    //建立大堆将父节点向下调整
    //思路：从从后向上将父节点向下调整；
    //父节点表示：(usedSize-1-1)/2;
    //左孩子节点表示为2*parent+1
    //1.找出左右孩子节点中的哪个元素最大
    //2.将父节点与左右孩子节点的最大值进行比较；
    //       如果小于，将元素进行交换；随后将父节点跳到孩子节点的位置，直到最后一个节点
    //       如果大于，退出该次循环，进入到下一次循环
    public void creatHeap1(){
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            //parent:调整的起始位置；
            //usedSize：调整的结束位置
            siftDown1(parent,usedSize);
        }
    }
    public void siftDown1(int parent,int usedSize){
        int child=2*parent+1;
        while(child<usedSize){
            //比较左右节点
            //如果左节点小于右节点
            //将孩子节点++，到右节点的位置
            if(child+1<usedSize && elem[child]<elem[child+1]){
                child++;
            }
            //比较父节点与子节点
            //如果小于子节点，交换两元素位置
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                //交换完，将父节点等于下一个子节点，看下一个堆是否形成大堆，
                //如果没有，继续交换
                parent=child;
                child=2*parent+1;
            }else{
                //如果大于子节点，不调整
                break;
            }                          }
    }
    private void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;

}
    public void creatHeap2(){
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            //parent:调整的起始位置；
            //usedSize：调整的结束位置
            siftDown2(parent,usedSize);
        }
    }
    public void siftDown2(int parent,int usedSize){
        int child=2*parent+1;
        while(child<usedSize){
            if(child+1<usedSize && elem[child]>elem[child+1]){
                child++;
            }
            if(elem[child]<elem[parent]){
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }                          }
    }

    //堆的插入：
    //1.看位置是否已满，如果满了扩容；
    //2.插入元素：
           //将元素插入在最后一个节点后面，也就是在elem[usedSize]
           //随后将其进行向上调整；
           //向上调整：将子节点向上调整
    public void offer(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        siftUp(usedSize);
        usedSize++;
    }
    private boolean isFull(){
        return this.usedSize== elem.length;
    }
    //向上调整：
    //将子节点与父节点进行比较；
         //如果大于父节点，交换；随后减子节点跳到父节点的位置，父节点跳到父节点的位置
         //小于退出本次循环
    public void siftUp(int child){
         int parent=(child-1)/2;
         //循环条件：parent>=0
         while(parent>=0){
             if(elem[parent]<elem[child]){
                 swap(elem,parent,child);
                 child=parent;
                 parent=(child-1)/2;
             }else{
                 break;
             }
         }
    }
    //堆的删除：删除堆顶元素
    //思路

    //将堆顶元素与最后一个节点元素进行交换，也就是位置0的元素与位置usedSize的元素进行交换
    //交换后，只有0位置开始不是大堆，所以我们从0开始进行向下调整；
    //调整完将使用大小减小
    public int poll(){
          if(isEmpty()){
              return -1;
          }
          int val=elem[0];
          swap(elem,0,usedSize-1);
          siftDown1(0,usedSize-1);
          usedSize--;
          return val;
    }
    private boolean isEmpty(){
        return this.usedSize==0;
    }
    //获取堆顶元素
    public int peek(){
        if (isEmpty()){
            return -1;
        }
        return elem[0];
    }
    //堆的排序
    // 将最后一个元素与第一个元素进行交换，也就是将最大值放在最后一个；
    //随后将交换在第一个位置的元素进行向下调整；
    //调整完，也就是倒数第二大的元素在堆顶，将其与倒二个元素进行交换，交换完调整，其他同样如此；
    public void heapSort(){
        int end=usedSize-1;
        while(end>0) {
            swap(elem, 0, end);
            siftDown1(0,end);
            end--;
        }
    }}
